With the widespread deployment of cryptocurrencies like Bitcoin, one of their supporting technologies, blockchain, becomes increasingly popular. It is a distributed consensus protocol that serves as a public ledger for cryptocurrency transactions. One of the problems is that their consensus protocols provide only probabilistic consistency guarantees.
In order to build a distributed consensus systems that provide strong consistency guarantees, financial institutions have begun to investigate the traditional Byzantine fault tolerant (BFT) protocols, which enable n servers to collectively act as a single machine even if f of them misbehave or malfunction in arbitrary (“Byzantine”) ways. However, practitioners usually hesitate to deploy such BFT protocols because of two reasons. The first reason is their poor scalability in terms of number of servers due to their intensive network communication which often involves as many as O(n2) messages for each request as for example disclosed in the non-patent literature of B.-G. Chun, P. Maniatis, S. Shenker, and J. Kubiatowicz, “Attested append only memory: Making adversaries stick to their word,” in Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, ser. SOSP '07. New York, N.Y., USA: ACM, 2007, pp. 189-204, available online: http://doi.acm.org/10.1145/1294261.1294280. The second reason is their high resource consumption, which requires n≥3f+1 servers to tolerate up to f faults as for example disclosed in the non-patent literature of M. Castro and B. Liskov, “Practical byzantine fault tolerance,” in Proceedings of the Third Symposium on Operating Systems Design and Implementation, ser. OSDI '99. Berkeley, Calif., USA: USENIX Association, 1999, pp. 173-186, available online http://dLacm.org/citation.cfm?id=296806.296824.
Arbitrary faults, usually called Byzantine faults, disclosed in the non-patent literature of E. Syta, I. Tamas, D. Visher, D. I. Wolinsky, L. Gasser, N. Gailly, and B. Ford, “Keeping authorities “honest or bust” with decentralized Witness cosigning,” in 37th IEEE Symposium on Security and Privacy, 2016, do not put any constraints on how processes fail. This sort of assumption about how processes fail, is specially adequate for systems where malicious attacks and intrusions can occur. For instance, an attacker might modify the behaviour of a process that he/she controls in order to change the outcome of the consensus algorithm, eventually causing the rest of the system to act in an erroneous way. When assuming Byzantine faults, instead of the more typical assumption of crash faults, this leads to more complex and challenging procedures.
Asynchrony might also be described as a non-assumption about timing properties, i.e., there is no need to make assumptions about the processing speeds of nodes and delays on message transmission. This (non-)assumption is important because attackers can often violate some timing properties by launching denial-of-service attacks against processes or communications. For instance, the attacker might delay the communication of a process for an interval, breaking some assumption about the timeliness of the system.
This system model—Byzantine faults and asynchrony—leads to an impossibility result, which says that consensus can not be deterministically solved in an asynchronous system if a single process can crash (often called the Fischer-Lynch-Paterson, FLP, result as described in the non-patent literature of T. C. Group, “Tpm main, part 1 design principles. specification version 1.2, revision 103.” 2007. The reason for the impossibility is that in an asynchronous system it is impossible to differentiate a crashed process from another that is simply slow (or connected by a slow network link).
Another conventional BFT-protocol called practical Byzantine fault tolerance (PBFT) for state machine replication services is shown in the non-patent literature of B.-G. Chun, P. Maniatis, S. Shenker, and J. Kubiatowicz, “Attested append only memory: Making adversaries stick to their word,” in Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, ser. SOSP '07. New York, N.Y., USA: ACM, 2007, pp. 189-204, available online: http://doi.acm.org/10.1145/1294261.1294280. Such a service is modeled as a state machine that is replicated across different servers in a distributed system. Each server maintains the service state and implements the service operations. Clients send requests to execute operations to the servers and PBFT ensures that all non-faulty servers execute the same operations in the same order.
In the non-patent literature of G. S. Veronese, M. Correia, A. N. Bessani, L. C. Lung, and P. Verissimo, “Efficient byzantine fault-tolerance,” IEEE Transactions on Computers, vol. 62, no. 1, pp. 16-30, January 2013, another conventional Byzantine Fault-Tolerant state machine replication protocol called MinBFT is described, which reduces the number of required servers from 3f+1 to 2f+1 and the number of communication rounds from 3 to 2. A trusted monotonic counter is used to build a Unique Sequential Identifier Generator (USIG), which is a local service that exists in every server. It assigns each requested message M a unique identifier (UI), which is a cryptographic signature of M together with a unique, monotonic and sequential counter c. These three properties imply that the USIG (1) will never assign the same identifier to two different messages (uniqueness), (2) will never assign an identifier that is lower than a previous one (monotonicity), and (3) will never assign an identifier that is not the successor of the previous one (sequentiality). These properties are guaranteed even if the server is compromised, and the service is implemented inside a trusted execution environment. In the non-patent literature of T.C. Group, “Tpm main, part 1 design principles, specification version 1.2, revision 103”, 2007, a Trusted Platform Module TPM is described to build a USIG service, which takes 797 ms to generate a signed counter. However one of the problems is the poor performance of the TPM-based USIG, partially due to the rate limiting. The TPM specification defines that the monotonic counter “must allow for 7 years of increments every 5 seconds” and “must support an increment rate of once every 5 seconds”. Another reason is the time that TPM takes to generate a signature being approximately 700 ms.